\section{Proofs for the triangulation process}
\label{sec:triangulation-10p}
In this section, we analyze the triangulation process on undirected
connected graphs, which is described by the following simple
iteration: In each round, for each node $u$, we add edge $(v,w)$
where $v$ and $w$ are drawn uniformly at random from
$\nei{t}{1}{u}$. The triangulation process yields the following
push-based resource discovery protocol. In each round, each node $u$
introduces two random neighbors $v$ and $w$ to one another.  The main
result of this section is that the triangulation process transforms an
arbitrary connected $n$-node graph to a complete graph in $O(n
\log^2 n)$ rounds with high probability.  We also establish an
$\Omega(n\log n)$ lower bound on the triangulation process for almost
all $n$-node graphs.

\subsection{Upper bound}
We obtain the $O(n \log^2 n)$ upper bound by proving that the minimum
degree of the graph increases by a constant factor (or equals $n-1$)
in $O(n \log n)$ steps.  Towards this objective, we study how the
neighbors of a given node connect to the two-hop neighbors of the
node.  We say that a node $v$ is {\bf {\em weakly tied}} to a set
of nodes $S$ if $v$ has less than $\md{0}/2$ edges to $S$
(i.e., $\dgi{t}{v}{S}<\md{0}/2$), and {\bf {\em strongly tied}} to $S$
if $v$ has at least $\md{0}/2$ edges to $S$ (i.e., $\dgi{t}{v}{S}
\ge\md{0}/2$).  (Recall that $\md{0}$ is the minimum degree at start of
round $0$.)
\begin{lemma}
\label{ob:strong-10p}
If $\md{0} \le \dg{t}{u} < (1+1/4)\md{0}$ and $w\in \nei{0}{1}{u}$ is
strongly tied to $\nei{t}{2}{u}$, then the probability that $u$
connects to a node in $\nei{t}{2}{u}$ through $w$ in round $t$ is at
least $2/(7n)$.
\junk{
\[\prob{u\mbox{ connects to a node in }\nei{t}{2}{u}\mbox{ through
  }w\mbox{ in round }t} \ge \frac{2}{7n} \]}
\end{lemma}
\begin{proof}
Since $w$ is strongly tied to $\nei{t}{2}{u}$,
$\dgi{t}{w}{\nei{t}{2}{u}} \ge \md{0}/2$.  Therefore, the probability
that $u$ connects to a node in $\nei{t}{2}{u}$ through $w$ in round
$t$ is
\begin{eqnarray*}
& = & \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{\dg{t}{w}} \cdot
\frac{1}{\dg{t}{w}} 
\;\;\; \ge \;\;\; \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{\dg{t}{w}}\cdot \frac{1}{n} 
\;\;\; \ge \;\;\; \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{|\nei{t}{1}{u}|+\dgi{t}{w}{\nei{t}{2}{u}}}\cdot \frac{1}{n} \\
& \ge & 
\frac{\dgi{t}{w}{\nei{t}{2}{u}}}{(1+1/4)\md{0} +
  \dgi{t}{w}{\nei{t}{2}{u}}}\cdot \frac{1}{n} 
\;\;\; \ge \;\;\; \frac{\md{0}/2}{(1+1/4)\md{0} + \md{0}/2}\cdot \frac{1}{n} 
\;\;\; = \;\;\; \frac{2}{7n}.
\end{eqnarray*}
\junk{
\begin{eqnarray*}
& & \prob{u\mbox{ connects to a node in }\nei{t}{2}{u}\mbox{ through
  }w\mbox{ in round }t} \\
&=& \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{\dg{t}{w}} \cdot
\frac{1}{\dg{t}{w}} \\
&\ge& \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{\dg{t}{w}}\cdot \frac{1}{n} \\
&\ge& \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{|\nei{t}{1}{u}|+\dgi{t}{w}{\nei{t}{2}{u}}}\cdot \frac{1}{n} \\
&\ge& \frac{\dgi{t}{w}{\nei{t}{2}{u}}}{(1+1/4)\md{0} +
  \dgi{t}{w}{\nei{t}{2}{u}}}\cdot \frac{1}{n} \\
&\ge& \frac{\md{0}/2}{(1+1/4)\md{0} + \md{0}/2}\cdot \frac{1}{n} \\
&=& \frac{2}{7n}
\end{eqnarray*}}
\end{proof}

\begin{lemma}
\label{ob:weak-10p}
If $\md{0} \le \dg{t}{u} < (1+1/4)\md{0}$, $w\in \nei{0}{1}{u}$ is
weakly tied to $\nei{t}{2}{u}$, and $v\in\nei{0}{2}{u}\cap
\nei{0}{1}{w}$, then the probability that $u$ connects to $v$ through
$w$ in round $t$ is at least $1/(4\md{0}^2)$.
\junk{
\[\prob{u\mbox{ connects to node in }v\mbox{ through }w\mbox{ in
    round }t} \ge \frac{1}{4\md{0}^2} \]
}
\end{lemma}
\begin{proof}
Since $w$ is weakly tied to $\nei{t}{2}{u}$ and $\dg{t}{w}$, is at
most $|\nei{t}{1}{u}| + \dgi{t}{w}{\nei{t}{2}{u}}$, we obtain that
$\dg{t}{w}$ is at most $(1+1/4)\md{0} + \md{0}/2$.  Therefore, the
probability that $u$ connects to $v$ through $w$ in round $t$ is
\begin{eqnarray*}
= \frac{1}{\dg{t}{w}^2} \ge \frac{1}{\rb{(1+1/4)\md{0} + \md{0}/2}^2} 
\;\;\; \ge \;\;\; \frac{1}{\rb{7\md{0}/4}^2} 
\;\;\; \ge \;\;\; \frac{1}{4\md{0}^2}.
\end{eqnarray*}
\junk{
\begin{eqnarray*}
& & \prob{u\mbox{ connects to node in }v\mbox{ through }w\mbox{ in
    round }t} \\
&=& \frac{1}{\dg{t}{w}^2} \\
&\ge& \frac{1}{\rb{(1+1/4)\md{0} + \md{0}/2}^2} \\
&\ge& \frac{1}{\rb{7\md{0}/4}^2} \\
&\ge& \frac{1}{4\md{0}^2} 
\end{eqnarray*}
}
\end{proof}

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=6.5in]{triangulation.jpg}
  \caption{{\small This figure illustrates the different cases and
      relations between lemmas used in the proof of Theorem
      \ref{thm:triangulation-10p}. The shaded nodes in $\nei{t}{1}{u}$
      are strongly tied to $\nei{t}{2}{u}$. Others are weakly tied to
      $\nei{t}{2}{u}$.}}
  \label{fig:triangulation.proof-10p}
\end{center}
\end{figure}

For analyzing the growth in the degree of a node $u$, we consider
two overlapping cases.  The first case is when more than $\md{0}/4$
nodes of $\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$, and
the second is when less than $\md{0}/3$ nodes of $\nei{t}{1}{u}$
are strongly tied to $\nei{t}{2}{u}$.  The analysis for the first case
is relatively straightforward: when several neighbors of a node $u$
are strongly tied to $u$'s two-hop neighbors, then their triangulation
steps connect $u$ to a large fraction of these two-hop neighbors.

\begin{lemma}[{\bf When several neighbors are strongly tied to two-hop neighbors}]
\label{lem:triangle+case1-10p}
There exists $T = O(n \log n)$ such that if more than $\md{0}/4$ nodes
in $\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$ for all $t<
T$, then $\dg{T}{u} \ge (1+1/4)\md{0}$ with probability at least
$1-1/n^2$.
\end{lemma}
\begin{proof}
  If at any round $t< T$, $\dg{t}{u} \ge \rb{1+1/4}\md{0}$, then the
  claim of the lemma holds. In the remainder of this proof, we assume
  $\dg{t}{u} < \rb{1+1/4}\md{0}$ for all $t < T$. Let $w\in
  \nei{t}{1}{u}$ be a node that is strongly tied to
  $\nei{t}{2}{u}$. By Lemma \ref{ob:strong-10p} we know that
\[ \prob{u\mbox{ connects to a node in }\nei{t}{2}{u}\mbox{ through
  }w\mbox{ in round } t} \ge \frac{2}{7n} > \frac{1}{6n}\]
We have more than $\md{0}/4$ such $w$'s in $\nei{t}{1}{u}$, each of
which independently executes a triangulation step in any given round.
Consider a run of $T_1 = 72 n\ln n/\md{0}$ rounds.  This implies at
least $18 n \ln n$ attempts to add an edge between $u$ and a node in
$\nei{t}{2}{u}$.  Thus,
\begin{eqnarray*}
\prob{u\mbox{ connects to a node in }\nei{t}{2}{u}\mbox{ after
  }T_1\mbox{ rounds}} \ge 1-\rb{1-\frac{1}{6n}}^{18 n \ln n} \ge 1- e^{-3\ln n} = 1 - \frac{1}{n^3}.
\end{eqnarray*}
If a node that is two hops away from $u$ becomes a neighbor of $u$ by
round $t$, it is no longer in $\nei{t}{2}{u}$.  Therefore, in $T=T_1
\md{0}/4 = O(n\log n)$ rounds, $u$ will connect to at least $\md{0}/4$
new nodes with probability at least $1-1/n^2$, i.e., $\dg{T}{u}\ge
\rb{1+1/4}\md{0}$.
\end{proof}
We next consider the second case where less than $\md{0}/3$ neighbors
of a given node $u$ are strongly tied to the two-hop neighborhood of
$u$.  This case is more challenging since the neighbors of $u$ that
are weakly tied may not contribute many new edges to $u$.  We break
the analysis of this part into two subcases based on whether there is
at least one neighbor of $u$ that is strongly tied to
$\nei{0}{2}{u}$. Figure \ref{fig:triangulation.proof-10p} illustrates
the different cases and lemmas used in the proof of Theorem
\ref{thm:triangulation-10p}.

\begin{lemma}[{\bf When few neighbors are strongly tied to two-hop neighbors}]
\label{lem:triangle+extro-10p}
There exists $T=O(n\log n)$ such that if less than $\md{0}/3$ nodes
in $\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$ for all $t <
T$, and there exists a node $v_0\in \nei{0}{1}{u}$ that is strongly
tied to $\nei{0}{2}{u}$, then $\dg{T}{u} \ge \rb{1+1/8}\md{0}$ with
probability at least $1-1/n^2$.
\end{lemma}
\begin{proof}
If at any point $t < T$, $\dg{T}{u} \ge \rb{1+1/8}\md{0}$, then the
claim of the lemma holds. In the remainder of this proof, we assume
$\dg{T}{u} < \rb{1+1/8}\md{0}$ for all $t < T$.  Let $S^0_t$ denote
the set of $v_0$'s neighbors in $\nei{t}{2}{u}$ which are strongly
tied to $\nei{t}{1}{u}$ at round $t$, $W^0_t$ denote the set of $v_0$'s
neighbors in $\nei{t}{2}{u}$ which are weakly tied to $\nei{t}{1}{u}$
at round $t$.

Consider any node $v$ in $S^0_t$.  Less than $\md{0}/3$ nodes in
$\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$, thus more than
$\md{0}/2 - \md{0}/3 = \md{0}/6$ neighbors of $v$ in $\nei{t}{1}{u}$
are weakly tied to $\nei{t}{2}{u}$. Let $w$ be one such weakly tied
node. By Lemma \ref{ob:weak-10p}, the probability that $u$ connects to
$v$ through $w$ in round $t$ is at least $1/(4\md{0}^2)$.  We have at
least $\md{0}/6$ such $w$'s, each of which executes a triangulation
step each round.  Consider $T=72\md{0}\ln n$ rounds of the process.
Then the probability that $u$ connects to $v$ in $T$ rounds is at
least
\[
1-\rb{1-\frac{1}{4\md{0}^2}}^{12 \md{0}^2 \ln n} \ge 1-e^{-3\ln n} 
= 1- \frac{1}{n^3}.
\]
Thus, if $|S^0_t|\ge \md{0}/8$, in an additional $O(n\log n)$ rounds,
$\dg{T}{u}\ge (1+1/8)\md{0}$ with probability at least
$1-1/n^2$. 

Therefore, in the remainder of the proof we consider the case where
$|S^0_t| < \md{0}/8$. Define $R^0_t = R^0_{t-1} \cup W^0_t$, $R^0_0 =
W^0_0$. If at least $\md{0}/8$ nodes in $R^0_t$ are connected to
$u$ at any time, then the claim of the lemma holds. Thus, in the
following we consider the case where $|R^0_t \cap \nei{t}{1}{u}| <
\md{0}/8$. From the definition of $R^0_t$, we can derive
\[|R^0_t| \ge |W^0_t| = \dgi{t}{v_0}{\nei{t}{2}{u}} - |S^0_t| \ge
\dgi{t}{v_0}{\nei{t}{2}{u}}  - \md{0}/8 \]
At round 0, $v_0$ is strongly tied to $\nei{0}{2}{u}$,
i.e., $\dgi{0}{v_0}{\nei{0}{2}{u}} \ge \md{0}/2$. Since $\md{0}\le \dg{t}{u} <
(1+1/8)\md{0}$, we have 
\[ \dgi{t}{v_0}{\nei{t}{2}{u}} \ge \dgi{t}{v_0}{\nei{0}{2}{u}} - \md{0}/8
  \ge 3\md{0}/8\]

Let $e_1$ denote the event $\cub{u\mbox{ connects to a node in
  }R^0_t\setminus \nei{t}{1}{u}\mbox{ through }v_0\mbox{ in round }t}$.
\begin{eqnarray*}
\prob{e_1} &=& \frac{|R^0_t\setminus \nei{t}{1}{u}|}{\dg{t}{v_0}} \cdot
\frac{1}{\dg{t}{v_0}} 
\;\;\; = \;\;\; \frac{|R^0_t| - |R^0_t \cap \nei{t}{1}{u}|}{\dg{t}{v_0}} \cdot
\frac{1}{\dg{t}{v_0}} \\
& \ge & \frac{|R^0_t| - |R^0_t \cap \nei{t}{1}{u}|}{\dg{t}{v_0}} \cdot
\frac{1}{n} 
\;\;\;= \;\;\; \frac{|R^0_t| - |R^0_t \cap \nei{t}{1}{u}|}{\abs{\nei{t}{1}{u}}+\dgi{t}{v_0}{\nei{t}{2}{u}}} \cdot
\frac{1}{n} \\
& \ge & \frac{|R^0_t| - \md{0}/8}{\abs{\nei{t}{1}{u}}+\dgi{t}{v_0}{\nei{t}{2}{u}}} \cdot
\frac{1}{n} 
\;\;\; \ge \;\;\; \frac{\dgi{t}{v_0}{\nei{t}{2}{u}}  - \md{0}/8 - \md{0}/8}{\abs{\nei{t}{1}{u}}+\dgi{t}{v_0}{\nei{t}{2}{u}}} \cdot
\frac{1}{n} \\
&\ge& \frac{3\md{0}/8 - \md{0}/8 - \md{0}/8}{\abs{\nei{t}{1}{u}}+3\md{0}/8} \cdot
\frac{1}{n} 
\;\;\; \ge \;\;\;  \frac{3\md{0}/8 - \md{0}/8 - \md{0}/8}{(1+1/8)\md{0}+3\md{0}/8} \cdot
\frac{1}{n} 
\;\;\; = \;\;\;  \frac{1}{12n}
\end{eqnarray*}
Let $X_1$ be the number of rounds it takes for $e_1$ to occur. When
$e_1$ occurs, let $v_1$ denote a witness for $e_1$; i.e., if we use
$X_1$ to denote the round at which $e_1$ occurs, then let $v_1$ denote
a node in $R^0_{X_1} \setminus \nei{X_1}{1}{u}$ to which $u$ connects
through $v_0$ in round $X_1$.  Since $v_1$ is in $R^0_{X_1}$, it is
also in $W^0_{t_1}$ for some $t_1 \le X_1$; therefore, $v_1$ is
strongly tied to $\nei{t_1}{2}{u}\cap \nei{t_1}{3}{u}$. If
$\dgi{t}{v_1}{\nei{t}{2}{u}} < 3\md{0}/8$ at any point $t$, then
$\dg{t}{u}\ge (1+1/8)\md{0}$.  Thus, in the remainder of the proof, we
consider the case where $\dgi{t}{v_1}{\nei{t}{2}{u}}\ge
3\md{0}/8$. Let $S^1_t$ (resp., $W^1_t$) denote the set of $v_1$'s
neighbors in $\nei{t}{2}{u}$ that are strongly tied (resp., weakly
tied) to $\nei{t}{1}{u}$.  If $|S^1_t| \ge \md{0}/8$, then as we did
for the case $|S^0_t| \ge \md{0}/8$, we argue that in $O(n \log n)$
rounds, the degree of $u$ is at least $(1 + 1/8)\md{0}$ with
probability at least $1 - 1/n^2$.

Thus, in the remainder, we assume that $|S^1_t| < \md{0}/8$.  Define
$R^1_t = R^1_{t-1} \cup W^1_t$, $R^1_{t_1} = W^1_{t_1}$. Let $e_2$
denote the event $\cub{u\mbox{ connects to a node in }R^0_t\setminus
  \nei{t}{1}{u}(\mbox{or }R^1_t\setminus \nei{t}{1}{u})\mbox{ through
  }v_0(\mbox{or }v_1)\mbox{ in round }t}$. By the same calculation as
for $v_0$, we have $\prob{e_2} \ge 1/6n$.  Similarly, we can define
$e_3, X_3, e_4, X_4, \dots, e_{\md{0}/4}, X_{\md{0}/4}$, and obtain
that $\prob{e_i} \ge i/(12n)$. The total number of rounds for $u$ to
gain $\md{0}/4$ edges is bounded by $T=\sum_i X_i$.  By Lemma
\ref{lem:couponcorollary-10p}, $T\le 36n \ln n$ with probability at least
$1-1/n^2$, completing the proof.
\end{proof}

\begin{lemma}[{\bf When all neighbors are weakly tied to two-hop neighbors}]
\label{lem:triangle+case2-10p}
There exists $T = O(n\log n)$ such that if all nodes in
$\nei{t}{1}{u}$ are weakly tied to $\nei{t}{2}{u}$ for all $t< T$,
then $\dg{T}{u}\ge \min\cub{(1+1/8)\md{0}, n-1}$ with probability at
least $1-1/n^2$.
\end{lemma}
\begin{proof}
  If at any point $t < T$, $\dg{t}{u}\ge \min\cub{(1+1/8)\md{0},
    n-1}$, then the claim of this lemma holds.  In the remainder of
  this proof, we assume $\dg{t}{u} < \min\cub{(1+1/8)\md{0}, n-1}$ for
  all $t < T$.  \junk{ When there exists an strongly tied node in
    $\nei{t}{1}{u}$, by Lemma \ref{lem:triangle+extro-10p}, we know in
     $T=O(n\log n)$ rounds, $\dg{T}{u}\ge (1+1/8)\md{0}$, which proves
    this lemma. Thus, we now consider the case where all nodes in
    $\nei{0}{1}{u}$ are weakly tied to $\nei{t}{2}{u}$ for $t < T$.  }
  In the following, we first show, any node $v\in \nei{0}{2}{u}$
  will have at least $\md{0}/4$ edges to $\nei{T_1}{1}{u}$, where $T_1
  = O(n\log n)$. After that, $v$ will connect to $u$ in $T_2 = O(n\log
  n)$ rounds. Therefore, the total number of rounds used for $v$ to
  connect to $u$ is $T_3 = T_1 + T_2 = O(n\log n)$.

Node $v$ at least connects to one node in $\nei{0}{1}{u}$. Call it
$w_1$. Because all nodes in $\nei{t}{1}{u}$ are weakly tied to
$\nei{t}{2}{u}$, we have $\dgi{t}{w_1}{\nei{t}{1}{u}} \ge \md{0} -
\md{0}/2 = \md{0}/2$. If $\dgi{t}{w_1}{\nei{t}{1}{u}\setminus
  \nei{t}{1}{v}} < \md{0}/4$, then $v$ already has $\md{0}/4$ edges to
$\nei{t}{1}{u}$. Thus, in the following we consider the case where
$\dgi{t}{w_1}{\nei{t}{1}{u}\setminus \nei{t}{1}{v}} \ge \md{0}/4$. Let
$e_1$ denote the event $\cub{v\mbox{ connects to a node in
  }\nei{t}{1}{u}\setminus \nei{t}{1}{v}\mbox{ through }w_1}$.
\begin{eqnarray*}
\prob{e_1} &=& \frac{\dgi{t}{w_1}{\nei{t}{1}{u}\setminus\nei{t}{1}{v}}}{\dg{t}{w_1}} \cdot
\frac{1}{\dg{t}{w_1}} 
\;\;\; \ge \;\;\; \frac{\dgi{t}{w_1}{\nei{t}{1}{u}\setminus \nei{t}{1}{v}}}{\abs{\nei{t}{1}{u}} +
  \dgi{t}{w_1}{\nei{t}{2}{u}}} \cdot \frac{1}{\dg{t}{w_1}} \\
&\ge& \frac{\md{0}/4}{(1+1/8)\md{0} + \md{0}/2} \cdot
\frac{1}{\dg{t}{w_1}} 
\;\;\; \ge \;\;\; \frac{2}{13} \cdot \frac{1}{n} 
\;\;\; > \;\;\; \frac{1}{7n}
\end{eqnarray*}
Let $X_1$ be the number of rounds needed for $e_1$ to occur. When
$e_1$ occurs, let $w_2$ denote a witness for $e_1$; i.e., let $w_2$
denote a vertex in $\nei{t}{1}{u} \setminus \nei{t}{1}{v}$ to which
$v$ connects.  Note that here the value of $t$ is the round at which
the event occurs.  By our choice, $w_2$ is also weakly tied to
$\nei{t}{2}{u}$.  By an argument similar to the one in the above
paragraph, we have $\dgi{t}{w_2}{\nei{t}{1}{u}\setminus \nei{t}{1}{v}}
\ge \md{0}/4$. Let $e_2$ denote the event $\cub{v\mbox{ connects to a
    node in }\nei{t}{1}{u}\mbox{ through }w_1\mbox{ or }w_2}$. We have
$\prob{e_2} \ge 2/(7n)$.  Let $X_2$ be the number of rounds needed for
$e_2$ to occur. Similarly, we can define $e_3, X_3, \dots,
e_{\md{0}/4}, X_{\md{0}/4}$ and show $\prob{e_i} \ge i/(7n)$. Set $T_1
= \sum_i X_i$, which is the bound on the number of rounds needed for
$v$ to have at least $\md{0}/4$ neighbors in $\nei{t}{1}{u}$. By Lemma
\ref{lem:couponcorollary-10p}, $T_2\le 28n\ln n$ with probability at
least $1-1/n^3$. Now we show $v$ will connect to $u$ in $T_2$ rounds
after this. Notice that, all $w_i$'s are still weakly tied to
$\nei{t}{2}{u}$. By Lemma \ref{ob:weak-10p}, the probability that $u$
connects to $v$ through $w_i$ in round $t$ is at least
$1/(4\md{0}^2)$.  We have $w_1,w_2,\dots,w_{\md{0}/4}$ independently
executing a triangulation step each round. Consider $T_2 = 48\md{0}\ln
n$ rounds of the process. Then,
\begin{eqnarray*}
\prob{u\mbox{ connects to }v\mbox{ in }T_2\mbox{ rounds}} 
\ge 1-\rb{1-\frac{1}{4\md{0}^2}}^{12\md{0}^2\ln n} 
\ge 1-\frac{1}{n^3}.
\end{eqnarray*}
We have shown for any node $v\in \nei{0}{2}{u}$, it will connect to
$u$ in round $T_3=T_1+T_2$ with probability at least $1-1/n^3$. This
implies in round $T_3$, $u$ will connect to all nodes in
$\nei{0}{2}{u}$ with probability at least
$1-\abs{\nei{0}{2}{u}}/n^3$. Then, $\nei{0}{2}{u} \subseteq
\nei{T_3}{1}{u}, \nei{0}{3}{u} \subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}, \nei{0}{4}{u} \subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}\cup \nei{T_3}{3}{u}$.  We apply the above analysis
twice, and obtain that in round $T=3T_3=O(n\log n)$,
$\nei{0}{2}{u}\cup \nei{0}{3}{u}\cup \nei{0}{4}{u} \subseteq
\nei{T}{1}{u}$ with probability at least $1-\abs{\nei{0}{2}{u}\cup
  \nei{0}{3}{u}\cup \nei{0}{4}{u}}/n^3\ge 1-1/n^2$. By Lemma
\ref{lem:moreneighbor-10p}, $\abs{\nei{0}{2}{u}\cup \nei{0}{3}{u}\cup
  \nei{0}{4}{u}} \ge\min\cub{2\md{0}, n-1}$, thus completing the
proof.
\end{proof}

\begin{theorem}[{\bf Upper bound for triangulation process}]
\label{thm:triangulation-10p}
  For any connected undirected graph, the triangulation process
  converges to a complete graph in $O(n\log^2 n)$ rounds with high
  probability.
\end{theorem}
\begin{proof}
  We first show that in $O(n\log n)$ rounds, either the graph becomes
  complete or its minimum degree increases by a factor of at least
  $1/12$. Then we apply this argument $O(\log n)$ times to complete
  the proof.

  For each $u$ where $\dg{0}{u} <\min\cub{(1+1/8)\md{0}, n-1}$, we
  consider the following 2 cases.  The first case is if more than
  $\md{0}/3$ nodes in $\nei{0}{1}{u}$ are strongly tied to
  $\nei{0}{2}{u}$.  By Lemma \ref{lem:triangle+case1-10p}, there exists
  $T=O(n\log n)$ such that if at least $\md{0}/4$ nodes in
  $\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$ for $t<T$, then
  $\dg{T}{u}\ge (1+1/8)\md{0}$ with probability at least $1-1/n^2$.
  Whenever the condition is not satisfied, i.e., less than $\md{0}/4$
  nodes in $\nei{t}{1}{u}$ are strongly tied to $\nei{t}{2}{u}$, it
  means more than $\md{0}/3-\md{0}/4=\md{0}/12$ strongly tied nodes
  became weakly tied. By the definitions of strongly tied and weakly
  tied, this implies $\dg{T}{u} \ge (1+1/12)\md{0}$.

The second case is if less than $\md{0}/3$ nodes in $\nei{0}{1}{u}$
are strongly tied to $\nei{0}{2}{u}$.  By
Lemmas~\ref{lem:triangle+extro-10p} and~\ref{lem:triangle+case2-10p}, we know
that there exists $T=O(n\log n)$ such that if we remain in this case
for $T$ rounds, then $\dg{T}{u}\ge \min\cub{ (1+1/8)\md{0}, n-1}$ with
probability at least $1-1/n^2$.  Whenever the condition is not
satisfied, i.e., more than $\md{0}/3$ nodes in $\nei{t}{1}{u}$ are
strongly tied to $\nei{t}{2}{u}$, we move to the analysis in the first
case, and $\dg{T}{u}\ge (1+1/8)\md{0}$ in $T=O(n\log n)$ rounds with
probability at least $1-1/n^2$.

Combining the above 2 cases and applying a union bound, we obtain
$\md{T} \ge \min\cub{(1+1/8)\md{0},n-1}$ in $T=O(n\log n)$ rounds with
probability at least $1-1/n$.  We now apply the above argument $O(\log
n)$ times to obtain the desired $O(n\log^2 n)$ upper bound.
\end{proof}

\junk{
\begin{lemma}
[{\bf Lower bound for triangulation process}]
 For any connected undirected graph $G$ with minimum degree $\alpha
  n$ for some constant $\alpha$, with high probability the
  triangulation process takes $\Omega(n\log n)$ to complete when the
  number of missing edges (compared with complete graph) is at least
  $n$.
\end{lemma}
\begin{proof}
  For any missing edge $(u,v)$, look at a common neighbor of $u$ and
  $v$, referred as $w$. Then node $w$ connecting $u$ and $v$ in a
  triangulation step is a Bernoulli experiment. Because the minimum
  degree of $G$ is $\alpha n$, the probability of a success outcome is
  at most $1/ \rb{\alpha n}^2$. Let $k$ be the number of missing
  edges. In the following we argue there has to be $\Omega(n^2\ln n)$
  such Bernoulli trials before all $k$ missing edges to be added. The
  triangulation process can only carry out at most $n$ such Bernoulli
  trials in each step, thus we complete the proof of $\Omega(n\ln n)$
  lower bound. 

  Let random variable $X_i$ denote the number of trials for the $i$th
  missing edge to be added. Let $T$ be $\beta n^2\ln n$, where $\beta$
  is a constant to be specified later.
\begin{eqnarray*}
\prob{X_1\le T, X_2\le T, \dots, X_k \le T} &=& \sqb{1-\rb{1-\frac{1}{\rb{\alpha n}^2}}^T}^k \\
&=& \sqb{1-\rb{1-\frac{1}{\rb{\alpha n}^2}}^{\beta n^2\ln n}}^k \\
&\rightarrow& \rb{1-e^{-\frac{\beta}{\alpha^2} \ln n}}^k \\
&=& \rb{1-\frac{1}{n^{\beta / \alpha^2}}}^k \\
&\le& \rb{1-\frac{1}{n^{\beta / \alpha^2}}}^n
\end{eqnarray*}
Set $\beta = \alpha^2/2$. Then,
\[\prob{X_1\le T, X_2\le T, \dots, X_k \le T} \le
\rb{1-\frac{1}{\sqrt{n}}}^n \le e^{-\sqrt{n}} \rightarrow 0\]
This completes the proof of this lemma.
\end{proof}
}

\subsection{Lower bound}
The proof of the following theorem is in
Appendix~\ref{app:triangulation}.

\begin{theorem}
[{\bf Lower bound for triangulation process}]
\label{thm:tri+lower-10p}
For any connected undirected graph $G$ that has $k \ge 1$ edges less
than the complete graph the triangulation process takes $\Omega(n \log
k)$ steps to complete with probability at least $1 - O\rb{e^{-k^{1/4}}}$.
\end{theorem}

\junk{
\begin{proof}
  We first observe that during the triangulation process there is a 
  time $t$ when the number of missing edges is at least $m = O(\sqrt{k})$
  and the minimum degree is at least $n/3$. If $k<\frac{2}{3} n$ then 
  this is true initially and for larger $k$ this is true at the first 
  time $t$ the minimum degree is large enough. The second case follows since
  the degree of a node (and thus also the minimum degree) can at most
  double in each step guaranteeing that the minimum degree is not larger
  than $\frac{2}{3}n$ at time $t$ also implying that at least $\frac{n}{3} = \Omega(\sqrt{k})$
  edges are still missing. 
  
  Given the bound on the minimum degree any missing edge $\{u,v\}$ is added 
  by a fixed node $w$ with probability at most $\frac{9}{2n^2}$.
  Since there are at most $n-2$ such nodes the probability that a missing edge
  gets added is at most $\frac{9}{2n}$. To analyze the time needed for all missing
  edges to be added we denote with $X_i$ the random variable
  counting the number of steps needed until the $i$th of the $m$ missing edges is added.
  We would like to analyze $\prob{X_1\le T, X_2\le T, \dots, X_m \le T}$ for an 
  appropriately chosen number of steps $T$. Note that the
  events $X_i < T$ and $X_j <T$ are not independent and indeed can be positively
  or negatively correlated. Nevertheless, independent of the conditioning onto 
  any of the events $X_j < T$, we have that $\prob{X_1 \le T} \leq 1 - (1 - \frac{9}{2n})^T \leq 1 - \frac{1}{\sqrt{m}}$ for an appropriately chosen $T = \Omega(n \log m)$, where $m$ is again the number of missing edges at time $t$. Thus,
$$\prob{X_1\le T, X_2\le T, \dots, X_m \le T} =$$
$$= \prob{X_1\le T| X_2\le T, \dots, X_m \le T} \cdot \prob{X_2 \le T | X_3, \dots, X_m \le T} \cdot \ldots \cdot \prob{X_m \le T} $$
$$\leq \rb{1-\frac{1}{\sqrt{m}}}^m \; = \; O\rb{e^{-\sqrt{m}}} \; = \; O\rb{e^{-k^{1/4}}}$$


This shows that the triangulation process takes with probability at least $1-O\rb{e^{-k^{1/4}}}$ at least $\Omega(n \log m) = O(n \log k)$ steps to complete. 
\end{proof}
}
